МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ національний університет “Львівська політехніка”
Лабораторна робота № 4 Аналіз складності алгоритмів № варіанта = [(день народження) + (ASCII–код першої літери прізвища – велика латинська літера) ] % 30 + 1= = (14 + 84)%30 + 1 = 9 Львів – 2012 1. МЕТА РОБОТИ Оволодіти методикою аналізу складності основних алгоритмічних конструкцій. Навчитись обчислювати функцію трудомісткості. Ознайомитись з класифікацією алгоритмів на основі функції трудомісткості. Опанувати методику аналізу розроблених алгоритмів на предмет їх складності. 2. ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ Завдання Розробити алгоритм розв'язання задачі згідно з індивідуальним завданням. Визначити до якого класу (підкласу) належить цей алгоритм в залежності від тих факторів, що впливають на значення функції трудомісткості. Знайти функцію трудомісткості алгоритму, використовуючи методику аналізу основних алгоритмічних конструкцій та визначення набору "елементарних" операцій. Визначити часову складність алгоритму для великих розмірів вхідних даних. Для її позначення використати нотацію Ландау (велике O). Навести назву асимптотичного класу ефективності алгоритму. Пояснити, як збільшиться час роботи алгоритму при подвоєнні розміру задачі. Побудувати графік функції трудомісткості для різних значень n. Вибір варіанту індивідуального завдання № варіанта = [(день народження) + (ASCII–код першої літери прізвища – велика латинська літера) ] % 30 + 1 = 9 Два масиви дiйсних чисел x та y впорядкованi по зростанню значень елементiв. Об'єднати цi масиви в один масив z так, щоб вони знову були впорядкованi по зростанню. 3. Алгоритм розв’язання задачі З елементiв вхiднiх масивiв формуємо новий масив z. Для цього порiвнюємо кожен i-тий елемент масиву x[], де i=0,1,2...n з кожним j-тим елементом масиву y[], де j=0,1,2...n: якщо x[i]<y[j] - то наступний елемент масиву z дорiвнює x[i] i i=i+1, а якщо x[i]<y[j]- то наступний елемент масиву z дорiвнює y[j] i j=j+1. 4. Дослідження складності алгоритму i=0;  1 операція  while(i<n){ 1 операція. Всього n проходів циклу  if(x[i]<y[j]){ 3 операції на кожний прохід циклу while  z[k]=x[i]; 3 операції на кожний прохід циклу while   i++; 2 операції на кожний прохід циклу while   k++;} 2 операції на кожний прохід циклу while  else{   if(j<n){ 1 операція  z[k]=y[j]; 3 операції на кожний прохід циклу while   j++; 2 операції на кожний прохід циклу while   k++;}} 2 операції на кожний прохід циклу while  }   if(j<n){ 1 операція  while(j<n){ 1 операція. Всього n-j проходів циклу  z[k]=y[j]; 3 операції на кожний прохід циклу while   j++; 2 операції на кожний прохід циклу while   k++;}} 2 операції на кожний прохід циклу while   Стосовно операцій порівняння i переприсвоєння цей алгоритм є кількісно-залежним, оскільки завжди треба перевiряти i переприсвоїти всі n елементів обидвох масивiв. Цей алгоритм виконує однакову кількість операцій при фіксованому значенні n. Таким чином, він є кількісно-залежним і належить до класу N. Функція трудомісткості обчислюється для цього алгоритму за формулою:
O(n²)(Квадратичний) - квадратичне зростання — подвоєння розміру задачі вчетверо збільшує необхідний час 5. Результати виконання програми Висновки Пiд час виконання даної лабораторної я оволоділа методикою аналізу складності основних алгоритмічних конструкцій, навчилась обчислювати функцію трудомісткості, ознайомилась з класифікацією алгоритмів на основі функції трудомісткості, опанувала методику аналізу розроблених алгоритмів на предмет їх складності. Додатки #include<stdio.h> #include<conio.h> #include<iostream> using namespace std; int main() { int i,j=0,k=0,const n=10; int x[10]={1,...